//给你一个数组 nums ，请你完成两类查询。 
//
// 
// 其中一类查询要求 更新 数组 nums 下标对应的值 
// 另一类查询要求返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元素的 和 ，其中 left <= right 
// 
//
// 实现 NumArray 类： 
//
// 
// NumArray(int[] nums) 用整数数组 nums 初始化对象 
// void update(int index, int val) 将 nums[index] 的值 更新 为 val 
// int sumRange(int left, int right) 返回数组 nums 中索引 left 和索引 right 之间（ 包含 ）的nums元
//素的 和 （即，nums[left] + nums[left + 1], ..., nums[right]） 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：
//["NumArray", "sumRange", "update", "sumRange"]
//[[[1, 3, 5]], [0, 2], [1, 2], [0, 2]]
//输出：
//[null, 9, null, 8]
//
//解释：
//NumArray numArray = new NumArray([1, 3, 5]);
//numArray.sumRange(0, 2); // 返回 1 + 3 + 5 = 9
//numArray.update(1, 2);   // nums = [1,2,5]
//numArray.sumRange(0, 2); // 返回 1 + 2 + 5 = 8
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 3 * 104 
// -100 <= nums[i] <= 100 
// 0 <= index < nums.length 
// -100 <= val <= 100 
// 0 <= left <= right < nums.length 
// 调用 update 和 sumRange 方法次数不大于 3 * 104 
// 
// Related Topics 设计 树状数组 线段树 数组 
// 👍 409 👎 0

package com.cute.leetcode.editor.cn;
public class RangeSumQueryMutable {
    public static void main(String[] args) {
        int[] nums = {1,2,3,6,5};
        NumArray numArray = new RangeSumQueryMutable().new NumArray(nums);

    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 使用树状数组解决单点修改求和的问题
     * 使用二进制分解去查询和更新
     */
    class NumArray {
        // 树状数组，为了防止0进入死循环，将数组的尺寸设置为n + 1
        int[] tree;
        // 返回最低位的1，二进制分解，lowbit返回的值一定是2的次幂
        // 根据最低位判断影响到的位置
        private int lowbit(int index){
            return index & -index;
        }
        // 查找前缀和
        private int query(int index){
            int ans = 0;
            for (int i = index; i > 0; i -= lowbit(i)) ans += tree[i];
            return ans;
        }
        // 更新修改index受到影响的前缀和
        private void insert(int index, int val){
            for (int i = index; i <= n; i += lowbit(i)) tree[i] += val;
        }

        int[] nums;
        int n;
        public NumArray(int[] nums) {
            this.nums = nums;
            n = nums.length;
            tree = new int[n + 1];
            // 初始化树状数组
            for (int i = 0; i < n; i++) insert(i + 1, nums[i]);
        }

        public void update(int index, int val) {
            insert(index + 1, val - nums[index]);
            nums[index] = val;
        }

        public int sumRange(int left, int right) {
            return query(right + 1) - query(left);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}